Адміністрація вирішила продати даний сайт. За детальною інформацією звертайтесь за адресою: rozrahu@gmail.com

ЛАБОРАТОРНА РОБОТА № 1 на тему: "Машина Поста"

Інформація про навчальний заклад

ВУЗ:
Національний університет Львівська політехніка
Інститут:
ІКНІ
Факультет:
Комп’ютерні науки
Кафедра:
Кафедра САПР

Інформація про роботу

Рік:
2015
Тип роботи:
Лабораторна робота
Предмет:
Теорiя алгоритмiв i математичнi основи представленння знань
Група:
КН 2
Варіант:
7

Частина тексту файла

Прізвище: Мороз Ім'я: Андрій Група: КН-26 Дата захисту: 16.12.2015р. Кафедра: САПР Дисципліна: Теорія алгоритмів Перевірив: Андрущак Н.А. ЛАБОРАТОРНА РОБОТА № 1 на тему: "Машина Поста" МЕТА РОБОТИ Мета роботи – вивчення формального визначення поняття алгоритму, пов’язаного із введеною Емілем Постом спеціальної математичної конструкції (машина Поста) і постулюванням тези про еквівалентність такого формалізму і поняття «алгоритм». КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ Машина Поста — це абстрактна (тобто така, що не існує в арсеналі техніки), але дуже проста обчислювальна машина. Машина Поста, не дивлячись на зовнішню простоту, може здійснювати різні обчислення, для чого потрібно задати початковий стан каретки і програму, яка виконає ці обчислення. Машиною ця математична конструкція названа тому, що при її побудові використовуються деякі поняття реальних машин (елемент пам’яті, команда тощо). Машина Поста складається із стрічки та каретки (яка також називається головкою зчитування/запису). Стрічка є безмежною і розділена на комірки однакового розміру (рис.2.1). / Рис. 2.1. Каретка завжди вказує на одну із комірок Комірка стрічки може бути порожньою, або у ній може перебувати мітка V. Каретка може пересуватися вздовж стрічки вліво і вправо Дії каретки підпорядковані програмі, яка складається з пронумерованого набору команд (команди можна представляти як рядки програми). Команди бувають шести типів: записати 1 (мітку), перейти до i-го рядка програми; записати 0 (стерти мітку), перейти до i-го рядка програми; переміститися вліво, перейти до i-го рядка програми; переміститися вправо, перейти до i-го рядка програми; зупинка; якщо 0, то перейти до i-го рядка програми, інакше перейти до j-го рядка програми. Наведемо перелік неприпустимих дій, які ведуть до аварійної зупинки машини: спроба записати 1 (мітку) в заповнену комірку; спроба стерти мітку в порожній комірці; нескінченне виконання (зациклення). Графічне представлення команд машини Поста → Крок вправо  ← Крок вліво  V Записати мітку  X Стерти мітку  ? a: b Переглянути комірку: якщо в комірці знаходиться 0, тоді перейти на команду з номером а, інакше на команду з номером b.  ! Зупинка  Програмою для машини Поста називається непорожній список послідовно пронумерованих команд наступної структури: n K m, де n - порядковий номер команди, K − дія, яка виконується кареткою, m - номер наступної команди, яку необхідно виконати. ІНДИВІДУАЛЬНЕ ЗАВДАННЯ Задано масив міток. Каретка оглядає 1-шу порожню комірку перед початком масиву. Розсунути масив таким чином, щоб після кожної мітки була порожня комірка. ТЕКСТ ПРОГРАМИ ? 2,3 → 1 X 4 → 5 ? 6,4 V 7 → 8 ? 10,9 ! ← 11 ? 12,10 → 3 РЕЗУЛЬТАТ ВИКОНАННЯ До запуску програми / Після запуску програми / ВИСНОВКИ На цій лабораторній роботі я ознайомився із машиною Поста, вивчив її склад, її команди, навчився записувати алгоритм у вигляді програми для неї, виконувати з їхньою допомогою прості математичні операції та маніпуляції з даними. В результаті чого виконав своє індивідуальне завдання та набув теоретичних і практичних навичок у роботі з машиною Поста.
Антиботан аватар за замовчуванням

13.02.2016 23:02

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини